Lower Bounds from State Space Relaxations for Concave Cost Network Flow Problems

In this paper we obtain Lower Bounds (LBs) to concave cost network flow problems. The LBs are derived from state space relaxations of a dynamic programming formulation, which involve the use of non-injective mapping functions guaranteing a reduction on the cardinality of the state space. The general state space relaxation procedure is extended to address problems involving transitions that go across several stages, as is the case of network flow problems. Applications for these LBs include: estimation of the quality of heuristic solutions; local search methods that use information of the LB solution structure to find initial solutions to restart the search (Fontes et al., 2003, Networks, 41, 221–228); and branch-and-bound (BB) methods having as a bounding procedure a modified version of the LB algorithm developed here, (see Fontes et al., 2005a). These LBs are iteratively improved by penalizing, in a Lagrangian fashion, customers not exactly satisfied or by performing state space modifications. Both the penalties and the state space are updated by using the subgradient method. Additional constraints are developed to improve further the LBs by reducing the searchable space. The computational results provided show that very good bounds can be obtained for concave cost network flow problems, particularly for fixed-charge problems.     

凹整数规划的分枝定界解法

凹整数规划是一类重要的非线性整数规划问题，也是在经济和管理中有着广泛应用的最优化问题．本文主要研究用分枝定界方法求解凹整数规划问题，这一方法的基本思想是对目标函数进行线性下逼近，然后用乘子搜索法求解连续松弛问题．数值结果表明，用这种分枝定界方法求解凹整数规划是有效的．     

Some remarks on the Jensen-Hadamard inequalities and applications

We provide some inequalities and integral inequalities connected to the Jensen-Hadamard inequalities for convex functions. In particular, we give some refinements to these inequalities. Some natural applications and further extensions are given.

---

Sunto Forniamo alcune diseguaglianze e diseguaglianze integrali connesse alle dise-gueglianze di Jensen-Hadamard per funzioni convesse. In particolare, diamo qualche miglioramento di queste diseguaglianze. Alcune applicazioni naturali ed ulteriori estensioni sono date.

     

Corrected mirror systems with double reflection

We propose objectives consisting of two mirrors with central holes for passage of a light beam. The optical layout ensures multiple reflection of rays from both mirrors. We consider several approaches to calculating the design parameters for which three and four aberrations do not occur. The objectives can be used in optical devices operating in the UV and IR regions of the spectrum. __________ Translated from Zhurnal Prikladnoi Spektroskopii, Vol. 74, No. 2, pp. 267–270, March–April, 2007.     

凹角区域双曲外问题的精确人工边界条件

研究一类凹角区域双曲型外问题的数值方法.先用Newmark方法对时间进行离散化,在每个时间步求解一个椭圆外问题.然后引入人工边界,并获得精确的人工边界条件.给出半离散化问题的变分问题,证明了变分问题的适定性,并给出了误差估计.最后给出数值例子,以示该方法的可行性与有效性.     

解可分离约束双凹规划问题的一种外逼近方法[英文]

在本文中，我们提出了双凹规划问题和更一般的广义凹规划问题。我们给出了双凹规划问题的整体最优性条件，并构造了一个有限终止外逼近算法。     

The Generalized KKM Map and Its Applications to Variational Inequalities

In this paper,applying the concept of generalized KKM map,we study problems ofvariational inequalities.We weaken convexity(concavity)conditions for a functional of two variables■(x,y)in the general variational inequalities.Last,we show a proof of non-topological degree meth-od of acute angle principle about monotone operator as an application of these results.     

A Finite Algorithm for Global Minimization of Separable Concave Programs

Researchers first examined the problem of separable concave programming more than thirty years ago, making it one of the earliest branches of nonlinear programming to be explored. This paper proposes a new algorithm that finds the exact global minimum of this problem in a finite number of iterations. In addition to proving that our algorithm terminates finitely, the paper extends a guarantee of finiteness to all branch-and-bound algorithms for concave programming that (1) partition exhaustively using rectangular subdivisions and (2) branch on the incumbent solution when possible. The algorithm uses domain reduction techniques to accelerate convergence; it solves problems with as many as 100 nonlinear variables, 400 linear variables and 50 constraints in about five minutes on an IBM RS/6000 Power PC. An industrial application with 152 nonlinear variables, 593 linear variables, and 417 constraints is also solved in about ten minutes.     

Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Dynamic complexity of optimal paths and discount factors for strongly concave problems

We study the relationship between the dynamical complexity of optimal paths and the discount factor in general infinite-horizon discrete-time concave problems. Given a dynamic systemx _t+1=h(x _t ), defined on the state space, we find two discount factors 0 < ^{* **} < 1 having the following properties. For any fixed discount factor 0 < < ^*, the dynamic system is the solution to some concave problem. For any discount factor ^** < < 1, the dynamic system is not the solution to any strongly concave problem. We prove that the upper bound ^** is a decreasing function of the topological entropy of the dynamic system. Different upper bounds are also discussed.This research was partially supported by MURST, National Group on Nonlinear dynamics in Economics and Social Sciences. The author would like to thank two anonymous referees for helpful comments and suggestions.